# 给定一个二维网格和一个单词，找出该单词是否存在于网格中。
#
#  单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
#
#
#
#  示例:
#
#  board =
# [
#   ['A','B','C','E'],
#   ['S','F','C','S'],
#   ['A','D','E','E']
# ]
#
# 给定 word = "ABCCED", 返回 true
# 给定 word = "SEE", 返回 true
# 给定 word = "ABCB", 返回 false
#
#
#
#  提示：
#
#
#  board 和 word 中只包含大写和小写英文字母。
#  1 <= board.length <= 200
#  1 <= board[i].length <= 200
#  1 <= word.length <= 10^3
#
#  Related Topics 数组 回溯算法
#  👍 543 👎 0


# leetcode submit region begin(Prohibit modification and deletion)
from typing import List


# todo

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:

        if not board or len(board) == 0:
            if not word or len(word) == 0:
                return True
            else:
                return False
        if len(word) == 0:
            return True

        m = len(board)
        n = len(board[0])
        # visited = [[False] * n] * m 是一种浅拷贝，每一列的数据都指向同一个，修改都会导致同一列的数据变化
        visited = [[False for _ in range(0, n)] for _ in range(0, m)]

        def dfs(board, i, j, index):
            nonlocal visited
            rs = len(board)
            cs = len(board[0])

            # 终止条件
            if index == len(word):
                return True

            # 越界或者当前字符被访问过 或者字符和匹配位置的单词不同
            print(i, j, index)
            if i < 0 or i >= rs or j < 0 or j >= cs or visted[i][j] or board[i][j] != word[index]:
                return False
            else:
                visited[i][j] = True

                if dfs(board, i + 1, j, index + 1):
                    return True

                if dfs(board, i - 1, j, index + 1):
                    return True

                if dfs(board, i, j + 1, index + 1):
                    return True

                if dfs(board, i, j - 1, index + 1):
                    return True

                visited[i][j] = False
                return False

        # 需要记录节点是否被访问过，记录当前访问的节点，记录当前匹配到哪个字符
        # 遍历每个节点，和 word 第一个字符相同，则开始深度查找
        for i in range(0, m):
            for j in range(0, n):
                if dfs(board, i, j, 0):
                    return True

        return False


# leetcode submit region end(Prohibit modification and deletion)


print(Solution().exist(
    [
        ["A", "B", "C", "E"],
        ["S", "F", "C", "S"],
        ["A", "D", "E", "E"]
    ],
    "ABCCED"))
